home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / grabst / util.c < prev   
C/C++ Source or Header  |  1990-03-06  |  9KB  |  384 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1986, 1988 Regents of the University of California
  5.    Copyright (c) 1989, Tera Computer Company
  6.  **/
  7.  
  8.   /* util.c -- miscellaneous useful routines */
  9.  
  10. #include "attribute.h"
  11. #include "digraph.h"
  12. #include "debug.h"
  13.  
  14. NODE *get_next_node(), *get_prev_node();
  15.  
  16. print_levels(digraph)
  17. DIGRAPH *digraph;
  18.   /* print_levels prints the nodes in each level of digraph.  */
  19. {
  20.     LEVEL *level;    /* each level */
  21.     MEMBER *member;  /* each member of each level */
  22.  
  23.     printf("\n\nDigraph Levels:\n");
  24.  
  25.     each_level(digraph, level)
  26.     loop
  27.         printf("   Level %d: ", Lno(level));
  28.  
  29.         each_member(level, member)
  30.         loop
  31.         printf(" %s", Name(member));
  32.         printf("[%1.2f, %1.2f]", Bc(member, UP), Bc(member, DOWN));
  33.         endloop
  34.  
  35.         printf("\n");
  36.     endloop
  37.  
  38.     printf("\n");
  39. } /* print_levels */
  40.  
  41. print_set(digraph, set)
  42. DIGRAPH *digraph;
  43. SET *set;
  44.   /* print_set prints the elements in set as nodes in digraph. */
  45. {
  46.     VNO vno;   /* each vno */
  47.  
  48.     each_element(set, vno)
  49.     loop
  50.         printf(" %s", Name(Node(digraph, vno)));
  51.     endloop
  52. } /* print_set */
  53.  
  54. PrintError(message)
  55. char *message;
  56.   /* PrintError prints message to standard error */
  57. {
  58.     fprintf(stderr, "\n** Error: %s\n", message);
  59. } /* PrintError */
  60.  
  61.   /**
  62.      the following four routines (get_edge, get_in_edge, num_edges, and
  63.      max_edges, are all remarkably alike.  Hence, if you change one, you
  64.      probably should be changing them all.
  65.  
  66.      These four routines are the best way to go from successor/ancestor
  67.      sets to outedges.  It is not a good idea to use the outedge or inedge
  68.      lists of a node when accessing the displayed graph, because the outedges
  69.      and inedges are only an abstract picture of the graph.  For example,
  70.      dummy and coalescer nodes have no in or out edges.  The 
  71.      successor/ancestor sets give a better picture of the displayed graph.
  72.  
  73.      When accessing a particular edge, get_edge should be used, unless
  74.      an inedge is needed, in which case get_in_edge should be used.
  75.      The normal way to access all edges between two nodes goes something
  76.      like this:
  77.      for (i = max_edges(from, to); i > 0; i--)
  78.      {
  79.          if ((edge = get_edge(digraph, from, to, i)) != NULL)
  80.          {
  81.          foo(edge);
  82.          }
  83.      }
  84.  
  85.      Note that it is necessary to check that the edge exists (i.e. check
  86.      that get_edge didn't return NULL), because the user could have deleted
  87.      an edge between two nodes.  The ordinalities of edges are not
  88.      compacted (except when the graph is laid out), because that would
  89.      create an inconsistency between the digraph structure, the 
  90.      data structure used by the InterViews interface, and the displayed
  91.      graph.  In other words, you'd have to update two data structures and
  92.      redraw some edges when deleting an edge, which is too much work.
  93.      The drawback is the extra checking for missing edges.
  94.  
  95.      if you want to check whether an edge exists between two nodes, use
  96.      num_edges.  Any other uses of num_edges should be viewed with suspicion.
  97.      num_edges should *never* be used to determine the valid ordinalities
  98.      for edges between two nodes since, as I noted above, there could
  99.      be gaps in the sequence.  In other words, max_edges ?= num_edges
  100.    **/
  101.  
  102. OUTEDGE *get_edge(digraph, node, tonode, ord)
  103. register DIGRAPH *digraph;
  104. register NODE *node, *tonode;
  105. int ord;
  106.   /**
  107.      finds the outedge from node to tonode of 
  108.      ordinality ord.  Outedges only go from proper nodes (not dummy or 
  109.      coalescer nodes) in the graph, so this is especially useful if either 
  110.      node or tonode is a dummy or coalescer. 
  111.    **/
  112. {
  113.     VNO nvno;
  114.     register OUTEDGE *outedge;
  115.  
  116.       /* if either node is a dummy, find the endpoints */
  117.     if (Is_dummy(node))
  118.     {
  119.     if ((node = get_prev_node(digraph, node)) == NULL)
  120.     {
  121.         return NULL;
  122.     }
  123.     }
  124.  
  125.     if (Is_dummy(tonode))
  126.     {
  127.         if ((tonode = get_next_node(digraph, tonode)) == NULL)
  128.     {
  129.         return NULL;
  130.     }
  131.     }
  132.  
  133.       /**
  134.      Ordinalities of edges from/to coalescer nodes are figured by
  135.      considering the elements in the expansion in order, with the
  136.      ordinality of an edge being the ordinality of the edge relative
  137.      to the element plus the sum of the ordinalities of edges in
  138.      previous elements.  So, for example, if a coalescer node contains
  139.      A, B, and C, and A has 3 edges to D, B has 1 edge, and C has 2,
  140.      the edges from the coalescer to D are considered to have the 
  141.      following ordinalities:
  142.          edges originally from A:  1-3
  143.            "    "          "   B:  4
  144.            "    "          "   C:  5-6
  145.      assuming vno(A) < vno(B) < vno(C)
  146.      Note that this is a recursive definition, so A, B, C, or D could be
  147.      coalescer nodes themselves.
  148.        **/
  149.     if (Coalescer(node))
  150.     {
  151.     int max;
  152.  
  153.     each_element(Expansion(node), nvno)
  154.     loop
  155.         if (ord <= (max = max_edges(Node(digraph, nvno), tonode)))
  156.         {
  157.         return get_edge(digraph, Node(digraph, nvno), tonode, ord);
  158.         }
  159.         else
  160.         {
  161.         ord -= max;
  162.         }
  163.     endloop;
  164.     }
  165.     else if (Coalescer(tonode))
  166.     {
  167.     int max;
  168.  
  169.     each_element(Expansion(tonode), nvno)
  170.     loop
  171.         if (ord <= (max = max_edges(node, Node(digraph, nvno))))
  172.         {
  173.         return get_edge(digraph, node, Node(digraph, nvno), ord);
  174.         }
  175.         else
  176.         {
  177.         ord -= max;
  178.         }
  179.     endloop;
  180.     }
  181.     else
  182.     {
  183.         all_out_edges(node, outedge)
  184.         loop
  185.             if (To_vno(outedge) == Vno(tonode) && Ord(outedge) == ord) 
  186.         {
  187.             return outedge;
  188.         }
  189.         endloop;
  190.     }
  191.  
  192.     return NULL;
  193. }
  194.  
  195. INEDGE *get_in_edge(digraph, node, tonode, ord)
  196. register DIGRAPH *digraph;
  197. register NODE *node, *tonode;
  198. int ord;
  199.   /**
  200.      finds the inedge from node to tonode of 
  201.      ordinality ord.  Inedges only go from proper nodes (not dummy or coalescer 
  202.      nodes) in the graph, so this is especially useful if either node or tonode 
  203.      is a dummy or coalescer. 
  204.    **/
  205. {
  206.     VNO nvno;
  207.     register INEDGE *inedge;
  208.  
  209.       /* if either node is a dummy, find the endpoints of the edge */
  210.     if (Is_dummy(node))
  211.     {
  212.     if ((node = get_prev_node(digraph, node)) == NULL)
  213.     {
  214.         return NULL;
  215.     }
  216.     }
  217.  
  218.     if (Is_dummy(tonode))
  219.     {
  220.         if ((tonode = get_next_node(digraph, tonode)) == NULL)
  221.     {
  222.         return NULL;
  223.     }
  224.     }
  225.  
  226.       /**
  227.      see get_edge for an explanation of edge ordinalities for coalescer
  228.      nodes
  229.        **/
  230.     if (Coalescer(node))
  231.     {
  232.     int max;
  233.  
  234.     each_element(Expansion(node), nvno)
  235.     loop
  236.         if (ord <= (max = max_edges(Node(digraph, nvno), tonode)))
  237.         {
  238.         return get_in_edge(digraph, Node(digraph, nvno), tonode, ord);
  239.         }
  240.         else
  241.         {
  242.         ord -= max;
  243.         }
  244.     endloop;
  245.     }
  246.     else if (Coalescer(tonode))
  247.     {
  248.     int max;
  249.  
  250.     each_element(Expansion(tonode), nvno)
  251.     loop
  252.         if (ord <= (max = max_edges(node, Node(digraph, nvno))))
  253.         {
  254.         return get_in_edge(digraph, node, Node(digraph, nvno), ord);
  255.         }
  256.         else
  257.         {
  258.         ord -= max;
  259.         }
  260.     endloop;
  261.     }
  262.     else
  263.     {
  264.         all_in_edges(tonode, inedge)
  265.         loop
  266.             if (From_vno(inedge) == Vno(node) && Ord(inedge) == ord) 
  267.         {
  268.             return inedge;
  269.         }
  270.         endloop;
  271.     }
  272.  
  273.     return NULL;
  274. }
  275.  
  276. num_edges(from, to)
  277. NODE* from;
  278. NODE* to;
  279.   /* finds the number of edges from from_node to to_node */
  280. {
  281.     VNO nvno;
  282.     OUTEDGE *outedge;
  283.     int count = 0;
  284.  
  285.     if (Is_dummy(from))
  286.     {
  287.     if ((from = get_prev_node(digraph, from)) == NULL)
  288.     {
  289.         return 0;
  290.     }
  291.     }
  292.  
  293.     if (Is_dummy(to))
  294.     {
  295.         if ((to = get_next_node(digraph, to)) == NULL)
  296.     {
  297.         return 0;
  298.     }
  299.     }
  300.  
  301.     if (Coalescer(from))
  302.     {
  303.     each_element(Expansion(from), nvno)
  304.     loop
  305.         count += num_edges(Node(digraph, nvno), to);
  306.     endloop;
  307.     }
  308.     else if (Coalescer(to))
  309.     {
  310.     each_element(Expansion(to), nvno)
  311.     loop
  312.         count += num_edges(from, Node(digraph, nvno));
  313.     endloop;
  314.     }
  315.     else
  316.     {
  317.         all_out_edges(from, outedge)
  318.         loop
  319.         if (To_vno(outedge) == Vno(to))
  320.         {
  321.             count++;
  322.         }
  323.         endloop;
  324.     }
  325.  
  326.     return count;
  327. }
  328.  
  329. max_edges(from, to)
  330. NODE* from;
  331. NODE* to;
  332.   /**
  333.      finds the maximum value for ordinality in an edge from from_node to 
  334.      to_node
  335.    **/
  336. {
  337.     VNO nvno;
  338.     OUTEDGE *outedge;
  339.     int max = 0;
  340.  
  341.     if (Is_dummy(from))
  342.     {
  343.     if ((from = get_prev_node(digraph, from)) == NULL)
  344.     {
  345.         return 0;
  346.     }
  347.     }
  348.  
  349.     if (Is_dummy(to))
  350.     {
  351.         if ((to = get_next_node(digraph, to)) == NULL)
  352.     {
  353.         return 0;
  354.     }
  355.     }
  356.  
  357.     if (Coalescer(from))
  358.     {
  359.     each_element(Expansion(from), nvno)
  360.     loop
  361.         max += max_edges(Node(digraph, nvno), to);
  362.     endloop;
  363.     }
  364.     else if (Coalescer(to))
  365.     {
  366.     each_element(Expansion(to), nvno)
  367.     loop
  368.         max += max_edges(from, Node(digraph, nvno));
  369.     endloop;
  370.     }
  371.     else
  372.     {
  373.         all_out_edges(from, outedge)
  374.         loop
  375.         if (To_vno(outedge) == Vno(to))
  376.         {
  377.             max = MAX(max, Ord(outedge));
  378.         }
  379.         endloop;
  380.     }
  381.  
  382.     return max;
  383. }
  384.